#include<bits/stdc++.h>
using namespace std;
using ll = long long;
/*
	题目描述：
	子序列累加和必须被7整除的最大累加和

	给定一个非负数组nums，可以任意选择数字组成子序列，但是子序列的累加和必须被7整除
	返回最大累加和

	数据范围：0 <= nums.length <= 1e5
	本题采用对数器验证
*/

//vector<int> RandomArray(int n, int val);
int f(vector<int>& nums, int i, int s);


// 暴力解（为了验证算法的正确性）
int maxSum1(vector<int>& nums)
{
	return f(nums, 0, 0);
}
int f(vector<int>& nums, int i, int sum)
{
	if (i == nums.size())
		return sum % 7 ? 0 : sum;
	return max(f(nums, i + 1, sum + nums[i]), f(nums, i + 1, sum));
}


// 动态规划解法
const int N = 1e6 + 10;
int dp[N][7];		// 以i结尾的子序列的累加和 % 7 == j，其最大的累加和
int maxSum2(vector<int>& nums)
{
	int n = nums.size();
	for (int j = 1; j <= 7; ++j) dp[0][j] = -1;
	for (int i = 1; i <= n; ++i)
	{
		int cur = nums[i - 1] % 7;
		for (int j = 0; j < 7; ++j)
		{
			int need = (j + 7 - cur) % 7;
			dp[i][j] =dp[i - 1][j];
			if (dp[i - 1][need] != -1)
				dp[i][j] = max(dp[i][j], dp[i - 1][need] + nums[i - 1]);
		}
	}
	return dp[n][0];
}


// 测试正确性

vector<int> RandomArray(int n, int val)
{
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		a[i] = rand() % val;
	return a;
}

int main1()
{
	srand(time(0));
	int n = 15;
	int v = 30;
	int testTime = 20;
	cout << "测试开始\n";
	for (int i = 0; i < testTime; ++i)
	{
		int len = rand() % n + i;
		vector<int> nums = RandomArray(len, v);
		ll begin1 = clock();
		int ret1 = maxSum1(nums);
		ll end1 = clock();
		ll begin2 = clock();
		int ret2 = maxSum2(nums);
		ll end2 = clock();
		if (ret1 != ret2)
		{
			cout << "该算法不正确\n";
			break;
		}
		cout << "第" << i + 1 << "个样例通过：\n";
		cout << "暴力解：" << end1 - begin1 << "\n";
		cout << "dp解：" << end2 - begin2 << '\n';
	}
	cout << "测试结束, 样例全部通过\n";
	return 0;
}


// 测试算法性能
int main()
{
	srand(time(0));
	int n = 1000000;
	int v = 3000000;
	int testTime = 200;
	cout << "测试开始\n";
	ll avgTime = 0, total = 0;
	for (int i = 1; i <= testTime; ++i)
	{
		int len = min(rand() % n + i * 20000, 1000000);
		vector<int> nums = RandomArray(len, v);
		ll begin = clock();
		int ret = maxSum2(nums);
		ll end = clock();
		cout << "第" << i + 1 << "个样例通过：\n";
		cout << "时间耗费：" << end - begin << "\n\n";
		total += end - begin;
	}
	cout << "平均消耗时间为： " << total / testTime << endl;
	return 0;
}